package com.wanghe.rank;

import java.util.Arrays;

/**
 * 希尔排序
 *
 * @author He Wang
 * @date 2020/06/14
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] a = {7, 9, 6, 5, 0, 4, 8, 6, 8, 5, 1};
        ShellSort shellSort = new ShellSort();
        shellSort.sort(a);
        System.out.println(Arrays.toString(a));
    }

    private void sort(int[] a) {

        for (int gap = a.length/2; gap > 0; gap/=2) {
            for (int i = 0; i < gap; i++) {
                for (int j = i + gap; j < a.length; j+=gap) {
                    if (a[j] < a[j - gap]) {
                        int tmp = a[j];
                        int k = 0;
                        for (k = j - gap; k >=0; k-=gap) {
                            if (a[k] >= tmp) {
                                a[k + gap] = a[k];
                            } else {
                                a[k+gap] = tmp;
                                break;
                            }
                        }
                        if (k < 0) {
                            a[k+gap] = tmp;
                        }
                    }
                }
            }
        }
    }

}
